﻿using System;
using System.Collections.Generic;
using System.Text;

namespace RoughJs.Helper
{
    public class BigInteger : IComparable
    {
        private int ival;
        private int[] words;
        private static int minFixNum = -100;
        private static int maxFixNum = 1024;
        private static int numFixNum = maxFixNum - minFixNum + 1;
        private static BigInteger[] smallFixNums = new BigInteger[numFixNum];
        public static BigInteger ZERO = smallFixNums[-minFixNum];
        private const int FLOOR = 1;
        private const int CEILING = 2;
        private const int TRUNCATE = 3;
        private const int ROUND = 4;
        // JDK1.2
        public static BigInteger ONE = smallFixNums[1 - minFixNum];

        private static bool IsLoad = false;
        private static void Init()
        {
            if (!IsLoad)
            {
                IsLoad = true;
                for (int i = numFixNum; --i >= 0; )
                    smallFixNums[i] = new BigInteger(i + minFixNum);
            }
            IsLoad = true;
        }

        private BigInteger()
        {
            Init();
        }
        /* Create a new (non-shared) BigInteger, and initialize to an int. */
        private BigInteger(int value)
        {
            Init();
            ival = value;
        }
        /* Create a new (non-shared) BigInteger, and initialize from a byte array. */
        public BigInteger(sbyte[] val)
        {
            Init();
            if (val == null || val.Length < 1)
                throw new FormatException();

            words = byteArrayToIntArray(val, val[0] < 0 ? -1 : 0);
            BigInteger result = make(words, words.Length);
            this.ival = result.ival;
            this.words = result.words;
        }

        /** Convert a big-endian byte array to a little-endian array of words. */
        private static int[] byteArrayToIntArray(sbyte[] bytes, int sign)
        {
            // Determine number of words needed.
            int[] words = new int[bytes.Length / 4 + 1];
            int nwords = words.Length;

            // Create a int out of modulo 4 high order bytes.
            int bptr = 0;
            int word = sign;
            for (int i = bytes.Length % 4; i > 0; --i, bptr++)
                word = (word << 8) | (bytes[bptr] & 0xff);
            words[--nwords] = word;

            // Elements remaining in byte[] are a multiple of 4.
            while (nwords > 0)
                words[--nwords] = bytes[bptr++] << 24 |
                                  (bytes[bptr++] & 0xff) << 16 |
                                  (bytes[bptr++] & 0xff) << 8 |
                                  (bytes[bptr++] & 0xff);
            return words;
        }
        private static BigInteger make(int[] words, int len)
        {
            if (words == null)
                return valueOf(len);
            len = BigInteger.wordsNeeded(words, len);
            if (len <= 1)
                return len == 0 ? ZERO : valueOf(words[0]);
            BigInteger num = new BigInteger();
            num.words = words;
            num.ival = len;
            return num;
        }
        private static int wordsNeeded(int[] words, int len)
        {
            int i = len;
            if (i > 0)
            {
                int word = words[--i];
                if (word == -1)
                {
                    while (i > 0 && (word = words[i - 1]) < 0)
                    {
                        i--;
                        if (word != -1) break;
                    }
                }
                else
                {
                    while (word == 0 && i > 0 && (word = words[i - 1]) >= 0) i--;
                }
            }
            return i + 1;
        }

        private static BigInteger alloc(int nwords)
        {
            BigInteger result = new BigInteger();
            if (nwords > 1)
                result.words = new int[nwords];
            return result;
        }

        public static BigInteger valueOf(long val)
        {
            Init();
            if (val >= minFixNum && val <= maxFixNum)
                return smallFixNums[(int)val - minFixNum];
            int i = (int)val;
            if ((long)i == val)
                return new BigInteger(i);
            BigInteger result = alloc(2);
            result.ival = 2;
            result.words[0] = i;
            result.words[1] = (int)(val >> 32);
            return result;
        }
        public int intValue()
        {
            if (words == null)
                return ival;
            return words[0];
        }

        public sbyte[] toByteArray()
        {
            // Determine number of bytes needed.  The method bitlength returns
            // the size without the sign bit, so add one bit for that and then
            // add 7 more to emulate the ceil function using integer math.
            sbyte[] bytes = new sbyte[(bitLength() + 1 + 7) / 8];
            int nbytes = bytes.Length;

            int wptr = 0;
            int word;

            // Deal with words array until one word or less is left to process.
            // If BigInteger is an int, then it is in ival and nbytes will be <= 4.
            while (nbytes > 4)
            {
                word = words[wptr++];
                for (int i = 4; i > 0; --i, word >>= 8)
                    bytes[--nbytes] = (sbyte)word;
            }

            // Deal with the last few bytes.  If BigInteger is an int, use ival.
            word = (words == null) ? ival : words[wptr];
            for (; nbytes > 0; word >>= 8)
                bytes[--nbytes] = (sbyte)word;

            return bytes;
        }


        public int bitLength()
        {
            if (words == null)
                return intLength(ival);
            return intLength(words, ival);
        }
        public static int intLength(int i)
        {
            return 32 - count_leading_zeros(i < 0 ? ~i : i);
        }
        /** Count the number of leading zero bits in an int. */
        public static int count_leading_zeros(int i)
        {
            if (i == 0)
                return 32;
            int count = 0;
            for (int k = 16; k > 0; k = k >> 1)
            {
                int j = MathKit.foo(i, k);
                if (j == 0)
                    count += k;
                else
                    i = j;
            }
            return count;
        }

        /** Calcaulte the Common Lisp "integer-length" function.
         * Assumes input is canonicalized:  len==BigInteger.wordsNeeded(words,len) */
        public static int intLength(int[] words, int len)
        {
            len--;
            return intLength(words[len]) + 32 * len;
        }
        private bool isZero()
        {
            return words == null && ival == 0;
        }
        private bool isNegative()
        {
            return (words == null ? ival : words[ival - 1]) < 0;
        }
        private static bool negate(int[] dest, int[] src, int len)
        {
            long carry = 1;
            bool negative = src[len - 1] < 0;
            for (int i = 0; i < len; i++)
            {
                carry += ((long)(~src[i]) & 0xffffffffL);
                dest[i] = (int)carry;
                carry >>= 32;
            }
            return (negative && dest[len - 1] < 0);
        }
        private void getAbsolute(int[] words)
        {
            int len;
            if (this.words == null)
            {
                len = 1;
                words[0] = this.ival;
            }
            else
            {
                len = this.ival;
                for (int i = len; --i >= 0; )
                    words[i] = this.words[i];
            }
            if (words[len - 1] < 0)
                negate(words, words, len);
            for (int i = words.Length; --i > len; )
                words[i] = 0;
        }
        public BigInteger pow(int exponent)
        {
            if (exponent <= 0)
            {
                if (exponent == 0)
                    return ONE;
                throw new ArithmeticException("negative exponent");
            }
            if (isZero())
                return this;
            int plen = words == null ? 1 : ival;  // Length of pow2.
            int blen = ((bitLength() * exponent) >> 5) + 2 * plen;
            bool negative = isNegative() && (exponent & 1) != 0;
            int[] pow2 = new int[blen];
            int[] rwords = new int[blen];
            int[] work = new int[blen];
            getAbsolute(pow2);  // pow2 = abs(this);
            int rlen = 1;
            rwords[0] = 1; // rwords = 1;
            for (; ; )  // for (i = 0;  ; i++)
            {
                // pow2 == this**(2**i)
                // prod = this**(sum(j=0..i-1, (exponent>>j)&1))
                if ((exponent & 1) != 0)
                { // r *= pow2
                    mul(work, pow2, plen, rwords, rlen);
                    int[] temp = work; work = rwords; rwords = temp;
                    rlen += plen;
                    while (rwords[rlen - 1] == 0) rlen--;
                }
                exponent >>= 1;
                if (exponent == 0)
                    break;
                // pow2 *= pow2;
                mul(work, pow2, plen, pow2, plen);
                int[] temp1 = work; work = pow2; pow2 = temp1;  // swap to avoid a copy
                plen *= 2;
                while (pow2[plen - 1] == 0) plen--;
            }
            if (rwords[rlen - 1] < 0)
                rlen++;
            if (negative)
                negate(rwords, rwords, rlen);
            return BigInteger.make(rwords, rlen);
        }
        public static int mul_1(int[] dest, int[] x, int len, int y)
        {
            long yword = (long)y & 0xffffffffL;
            long carry = 0;
            for (int j = 0; j < len; j++)
            {
                carry += ((long)x[j] & 0xffffffffL) * yword;
                dest[j] = (int)carry;
                carry = MathKit.foo2(carry, 32);
            }
            return (int)carry;
        }
        public static void mul(int[] dest,
                          int[] x, int xlen,
                          int[] y, int ylen)
        {
            dest[xlen] = mul_1(dest, x, xlen, y[0]);

            for (int i = 1; i < ylen; i++)
            {
                long yword = (long)y[i] & 0xffffffffL;
                long carry = 0;
                for (int j = 0; j < xlen; j++)
                {
                    carry += ((long)x[j] & 0xffffffffL) * yword
                      + ((long)dest[i + j] & 0xffffffffL);
                    dest[i + j] = (int)carry;
                    carry = MathKit.foo2(carry, 32);
                }
                dest[i + xlen] = (int)carry;
            }
        }


        /** Add two ints, yielding a BigInteger. */
        private static BigInteger add(int x, int y)
        {
            return valueOf((long)x + (long)y);
        }

        /** Add a BigInteger and an int, yielding a new BigInteger. */
        private static BigInteger add(BigInteger x, int y)
        {
            if (x.words == null)
                return BigInteger.add(x.ival, y);
            BigInteger result = new BigInteger(0);
            result.setAdd(x, y);
            return result.canonicalize();
        }

        /** Set this to the sum of x and y.
         * OK if x==this. */
        private void setAdd(BigInteger x, int y)
        {
            if (x.words == null)
            {
                set((long)x.ival + (long)y);
                return;
            }
            int len = x.ival;
            realloc(len + 1);
            long carry = y;
            for (int i = 0; i < len; i++)
            {
                carry += ((long)x.words[i] & 0xffffffffL);
                words[i] = (int)carry;
                carry >>= 32;
            }
            if (x.words[len - 1] < 0)
                carry--;
            words[len] = (int)carry;
            ival = wordsNeeded(words, len + 1);
        }

        /** Destructively add an int to this. */
        private void setAdd(int y)
        {
            setAdd(this, y);
        }

        private void realloc(int nwords)
        {
            if (nwords == 0)
            {
                if (words != null)
                {
                    if (ival > 0)
                        ival = words[0];
                    words = null;
                }
            }
            else if (words == null
                     || words.Length < nwords
                     || words.Length > nwords + 2)
            {
                int[] new_words = new int[nwords];
                if (words == null)
                {
                    new_words[0] = ival;
                    ival = 1;
                }
                else
                {
                    if (nwords < ival)
                        ival = nwords;
                    Array.Copy(words, 0, new_words, 0, ival);
                }
                words = new_words;
            }
        }

        private BigInteger canonicalize()
        {
            if (words != null
                && (ival = BigInteger.wordsNeeded(words, ival)) <= 1)
            {
                if (ival == 1)
                    ival = words[0];
                words = null;
            }
            if (words == null && ival >= minFixNum && ival <= maxFixNum)
                return smallFixNums[ival - minFixNum];
            return this;
        }

        /** Destructively set the value of this to a long. */
        private void set(long y)
        {
            int i = (int)y;
            if ((long)i == y)
            {
                ival = i;
                words = null;
            }
            else
            {
                realloc(2);
                words[0] = i;
                words[1] = (int)(y >> 32);
                ival = 2;
            }
        }

        /** Destructively set the value of this to the given words.
        * The words array is reused, not copied. */
        private void set(int[] words, int length)
        {
            this.ival = length;
            this.words = words;
        }

        /** Destructively set the value of this to that of y. */
        private void set(BigInteger y)
        {
            if (y.words == null)
                set(y.ival);
            else if (this != y)
            {
                realloc(y.ival);
                Array.Copy(y.words, 0, words, 0, y.ival);
                ival = y.ival;
            }
        }

        private static BigInteger neg(BigInteger x)
        {
            if (x.words == null && x.ival != int.MinValue)
                return valueOf(-x.ival);
            BigInteger result = new BigInteger(0);
            result.setNegative(x);
            return result.canonicalize();
        }

        public BigInteger negate()
        {
            return neg(this);
        }

        /** Add two BigIntegers, yielding their sum as another BigInteger. */
        private static BigInteger add(BigInteger x, BigInteger y, int k)
        {
            if (x.words == null && y.words == null)
                return valueOf((long)k * (long)y.ival + (long)x.ival);
            if (k != 1)
            {
                if (k == -1)
                    y = BigInteger.neg(y);
                else
                    y = BigInteger.times(y, valueOf(k));
            }
            if (x.words == null)
                return BigInteger.add(y, x.ival);
            if (y.words == null)
                return BigInteger.add(x, y.ival);
            // Both are big
            if (y.ival > x.ival)
            { // Swap so x is longer then y.
                BigInteger tmp = x; x = y; y = tmp;
            }
            BigInteger result = alloc(x.ival + 1);
            int i = y.ival;
            long carry = MPN.add_n(result.words, x.words, y.words, i);
            long y_ext = y.words[i - 1] < 0 ? 0xffffffffL : 0;
            for (; i < x.ival; i++)
            {
                carry += ((long)x.words[i] & 0xffffffffL) + y_ext; ;
                result.words[i] = (int)carry;
                carry = MathKit.foo2(carry, 32);
            }
            if (x.words[i - 1] < 0)
                y_ext--;
            result.words[i] = (int)(carry + y_ext);
            result.ival = i + 1;
            return result.canonicalize();
        }

        public BigInteger add(BigInteger val)
        {
            return add(this, val, 1);
        }

        public BigInteger subtract(BigInteger val)
        {
            return add(this, val, -1);
        }
        //private static bool negate(int[] dest, int[] src, int len)
        //{
        //    long carry = 1;
        //    bool negative = src[len - 1] < 0;
        //    for (int i = 0; i < len; i++)
        //    {
        //        carry += ((long)(~src[i]) & 0xffffffffL);
        //        dest[i] = (int)carry;
        //        carry >>= 32;
        //    }
        //    return (negative && dest[len - 1] < 0);
        //}
        private void setNegative(BigInteger x)
        {
            int len = x.ival;
            if (x.words == null)
            {
                if (len == int.MinValue)
                    set(-(long)len);
                else
                    set(-len);
                return;
            }
            realloc(len + 1);
            if (negate(words, x.words, len))
                words[len++] = 0;
            ival = len;
        }

        private static BigInteger times(BigInteger x, int y)
        {
            if (y == 0)
                return ZERO;
            if (y == 1)
                return x;
            int[] xwords = x.words;
            int xlen = x.ival;
            if (xwords == null)
                return valueOf((long)xlen * (long)y);
            bool negative;
            BigInteger result = BigInteger.alloc(xlen + 1);
            if (xwords[xlen - 1] < 0)
            {
                negative = true;
                negate(result.words, xwords, xlen);
                xwords = result.words;
            }
            else
                negative = false;
            if (y < 0)
            {
                negative = !negative;
                y = -y;
            }
            result.words[xlen] = MPN.mul_1(result.words, xwords, xlen, y);
            result.ival = xlen + 1;
            if (negative)
                result.setNegative();
            return result.canonicalize();
        }

        private static BigInteger times(BigInteger x, BigInteger y)
        {
            if (y.words == null)
                return times(x, y.ival);
            if (x.words == null)
                return times(y, x.ival);
            bool negative = false;
            int[] xwords;
            int[] ywords;
            int xlen = x.ival;
            int ylen = y.ival;
            if (x.isNegative())
            {
                negative = true;
                xwords = new int[xlen];
                negate(xwords, x.words, xlen);
            }
            else
            {
                negative = false;
                xwords = x.words;
            }
            if (y.isNegative())
            {
                negative = !negative;
                ywords = new int[ylen];
                negate(ywords, y.words, ylen);
            }
            else
                ywords = y.words;
            // Swap if x is shorter then y.
            if (xlen < ylen)
            {
                int[] twords = xwords; xwords = ywords; ywords = twords;
                int tlen = xlen; xlen = ylen; ylen = tlen;
            }
            BigInteger result = BigInteger.alloc(xlen + ylen);
            MPN.mul(result.words, xwords, xlen, ywords, ylen);
            result.ival = xlen + ylen;
            if (negative)
                result.setNegative();
            return result.canonicalize();
        }

        public BigInteger multiply(BigInteger y)
        {
            return times(this, y);
        }

        private static void divide(long x, long y,
                                   BigInteger quotient, BigInteger remainder,
                                   int rounding_mode)
        {
            bool xNegative, yNegative;
            if (x < 0)
            {
                xNegative = true;
                if (x == long.MinValue)
                {
                    divide(valueOf(x), valueOf(y),
                           quotient, remainder, rounding_mode);
                    return;
                }
                x = -x;
            }
            else
                xNegative = false;

            if (y < 0)
            {
                yNegative = true;
                if (y == long.MinValue)
                {
                    if (rounding_mode == TRUNCATE)
                    { // x != Long.Min_VALUE implies abs(x) < abs(y)
                        if (quotient != null)
                            quotient.set(0);
                        if (remainder != null)
                            remainder.set(x);
                    }
                    else
                        divide(valueOf(x), valueOf(y),
                                quotient, remainder, rounding_mode);
                    return;
                }
                y = -y;
            }
            else
                yNegative = false;

            long q = x / y;
            long r = x % y;
            bool qNegative = xNegative ^ yNegative;

            bool add_one = false;
            if (r != 0)
            {
                switch (rounding_mode)
                {
                    case TRUNCATE:
                        break;
                    case CEILING:
                    case FLOOR:
                        if (qNegative == (rounding_mode == FLOOR))
                            add_one = true;
                        break;
                    case ROUND:
                        add_one = r > ((y - (q & 1)) >> 1);
                        break;
                }
            }
            if (quotient != null)
            {
                if (add_one)
                    q++;
                if (qNegative)
                    q = -q;
                quotient.set(q);
            }
            if (remainder != null)
            {
                // The remainder is by definition: X-Q*Y
                if (add_one)
                {
                    // Subtract the remainder from Y.
                    r = y - r;
                    // In this case, abs(Q*Y) > abs(X).
                    // So sign(remainder) = -sign(X).
                    xNegative = !xNegative;
                }
                else
                {
                    // If !add_one, then: abs(Q*Y) <= abs(X).
                    // So sign(remainder) = sign(X).
                }
                if (xNegative)
                    r = -r;
                remainder.set(r);
            }
        }
        public long longValue()
        {
            if (words == null)
                return ival;
            if (ival == 1)
                return words[0];
            return ((long)words[1] << 32) + ((long)words[0] & 0xffffffffL);
        }

        /** Divide two integers, yielding quotient and remainder.
         * @param x the numerator in the division
         * @param y the denominator in the division
         * @param quotient is set to the quotient of the result (iff quotient!=null)
         * @param remainder is set to the remainder of the result
         *  (iff remainder!=null)
         * @param rounding_mode one of FLOOR, CEILING, TRUNCATE, or ROUND.
         */
        private static void divide(BigInteger x, BigInteger y,
                                   BigInteger quotient, BigInteger remainder,
                                   int rounding_mode)
        {
            if ((x.words == null || x.ival <= 2)
                && (y.words == null || y.ival <= 2))
            {
                long x_l = x.longValue();
                long y_l = y.longValue();
                if (x_l != long.MinValue && y_l != long.MinValue)
                {
                    divide(x_l, y_l, quotient, remainder, rounding_mode);
                    return;
                }
            }

            bool xNegative = x.isNegative();
            bool yNegative = y.isNegative();
            bool qNegative = xNegative ^ yNegative;

            int ylen = y.words == null ? 1 : y.ival;
            int[] ywords = new int[ylen];
            y.getAbsolute(ywords);
            while (ylen > 1 && ywords[ylen - 1] == 0) ylen--;

            int xlen = x.words == null ? 1 : x.ival;
            int[] xwords = new int[xlen + 2];
            x.getAbsolute(xwords);
            while (xlen > 1 && xwords[xlen - 1] == 0) xlen--;

            int qlen, rlen;

            int cmpval = MPN.cmp(xwords, xlen, ywords, ylen);
            if (cmpval < 0)  // abs(x) < abs(y)
            { // quotient = 0;  remainder = num.
                int[] rwords = xwords; xwords = ywords; ywords = rwords;
                rlen = xlen; qlen = 1; xwords[0] = 0;
            }
            else if (cmpval == 0)  // abs(x) == abs(y)
            {
                xwords[0] = 1; qlen = 1;  // quotient = 1
                ywords[0] = 0; rlen = 1;  // remainder = 0;
            }
            else if (ylen == 1)
            {
                qlen = xlen;
                // Need to leave room for a word of leading zeros if dividing by 1
                // and the dividend has the high bit set.  It might be safe to
                // increment qlen in all cases, but it certainly is only necessary
                // in the following case.
                if (ywords[0] == 1 && xwords[xlen - 1] < 0)
                    qlen++;
                rlen = 1;
                ywords[0] = MPN.divmod_1(xwords, xwords, xlen, ywords[0]);
            }
            else  // abs(x) > abs(y)
            {
                // Normalize the denominator, i.e. make its most significant bit set by
                // shifting it normalization_steps bits to the left.  Also shift the
                // numerator the same number of steps (to keep the quotient the same!).

                int nshift = MPN.count_leading_zeros(ywords[ylen - 1]);
                if (nshift != 0)
                {
                    // Shift up the denominator setting the most significant bit of
                    // the most significant word.
                    MPN.lshift(ywords, 0, ywords, ylen, nshift);

                    // Shift up the numerator, possibly introducing a new most
                    // significant word.
                    int x_high = MPN.lshift(xwords, 0, xwords, xlen, nshift);
                    xwords[xlen++] = x_high;
                }

                if (xlen == ylen)
                    xwords[xlen++] = 0;
                MPN.divide(xwords, xlen, ywords, ylen);
                rlen = ylen;
                MPN.rshift0(ywords, xwords, 0, rlen, nshift);

                qlen = xlen + 1 - ylen;
                if (quotient != null)
                {
                    for (int i = 0; i < qlen; i++)
                        xwords[i] = xwords[i + ylen];
                }
            }

            if (ywords[rlen - 1] < 0)
            {
                ywords[rlen] = 0;
                rlen++;
            }

            // Now the quotient is in xwords, and the remainder is in ywords.

            bool add_one = false;
            if (rlen > 1 || ywords[0] != 0)
            { // Non-zero remainder i.e. in-exact quotient.
                switch (rounding_mode)
                {
                    case TRUNCATE:
                        break;
                    case CEILING:
                    case FLOOR:
                        if (qNegative == (rounding_mode == FLOOR))
                            add_one = true;
                        break;
                    case ROUND:
                        // int cmp = compareTo(remainder<<1, abs(y));
                        BigInteger tmp = remainder == null ? new BigInteger() : remainder;
                        tmp.set(ywords, rlen);
                        tmp = shift(tmp, 1);
                        if (yNegative)
                            tmp.setNegative();
                        int cmp = compareTo(tmp, y);
                        // Now cmp == compareTo(sign(y)*(remainder<<1), y)
                        if (yNegative)
                            cmp = -cmp;
                        add_one = (cmp == 1) || (cmp == 0 && (xwords[0] & 1) != 0);
                        break;
                }
            }
            if (quotient != null)
            {
                quotient.set(xwords, qlen);
                if (qNegative)
                {
                    if (add_one)  // -(quotient + 1) == ~(quotient)
                        quotient.setInvert();
                    else
                        quotient.setNegative();
                }
                else if (add_one)
                    quotient.setAdd(1);
            }
            if (remainder != null)
            {
                // The remainder is by definition: X-Q*Y
                remainder.set(ywords, rlen);
                if (add_one)
                {
                    // Subtract the remainder from Y:
                    // abs(R) = abs(Y) - abs(orig_rem) = -(abs(orig_rem) - abs(Y)).
                    BigInteger tmp;
                    if (y.words == null)
                    {
                        tmp = remainder;
                        tmp.set(yNegative ? ywords[0] + y.ival : ywords[0] - y.ival);
                    }
                    else
                        tmp = BigInteger.add(remainder, y, yNegative ? 1 : -1);
                    // Now tmp <= 0.
                    // In this case, abs(Q) = 1 + floor(abs(X)/abs(Y)).
                    // Hence, abs(Q*Y) > abs(X).
                    // So sign(remainder) = -sign(X).
                    if (xNegative)
                        remainder.setNegative(tmp);
                    else
                        remainder.set(tmp);
                }
                else
                {
                    // If !add_one, then: abs(Q*Y) <= abs(X).
                    // So sign(remainder) = sign(X).
                    if (xNegative)
                        remainder.setNegative();
                }
            }
        }

        private void setInvert()
        {
            if (words == null)
                ival = ~ival;
            else
            {
                for (int i = ival; --i >= 0; )
                    words[i] = ~words[i];
            }
        }
        private void setNegative()
        {
            setNegative(this);
        }
        public BigInteger divide(BigInteger val)
        {
            if (val.isZero())
                throw new ArithmeticException("divisor is zero");

            BigInteger quot = new BigInteger();
            divide(this, val, quot, null, TRUNCATE);
            return quot.canonicalize();
        }
        private void setShiftLeft(BigInteger x, int count)
        {
            int[] xwords;
            int xlen;
            if (x.words == null)
            {
                if (count < 32)
                {
                    set((long)x.ival << count);
                    return;
                }
                xwords = new int[1];
                xwords[0] = x.ival;
                xlen = 1;
            }
            else
            {
                xwords = x.words;
                xlen = x.ival;
            }
            int word_count = count >> 5;
            count &= 31;
            int new_len = xlen + word_count;
            if (count == 0)
            {
                realloc(new_len);
                for (int i = xlen; --i >= 0; )
                    words[i + word_count] = xwords[i];
            }
            else
            {
                new_len++;
                realloc(new_len);
                int shift_out = MPN.lshift(words, word_count, xwords, xlen, count);
                count = 32 - count;
                words[new_len - 1] = (shift_out << count) >> count;  // sign-extend.
            }
            ival = new_len;
            for (int i = word_count; --i >= 0; )
                words[i] = 0;
        }
        private void setShiftRight(BigInteger x, int count)
        {
            if (x.words == null)
                set(count < 32 ? x.ival >> count : x.ival < 0 ? -1 : 0);
            else if (count == 0)
                set(x);
            else
            {
                bool neg = x.isNegative();
                int word_count = count >> 5;
                count &= 31;
                int d_len = x.ival - word_count;
                if (d_len <= 0)
                    set(neg ? -1 : 0);
                else
                {
                    if (words == null || words.Length < d_len)
                        realloc(d_len);
                    MPN.rshift0(words, x.words, word_count, d_len, count);
                    ival = d_len;
                    if (neg)
                        words[d_len - 1] |= -2 << (31 - count);
                }
            }
        }

        private void setShift(BigInteger x, int count)
        {
            if (count > 0)
                setShiftLeft(x, count);
            else
                setShiftRight(x, -count);
        }

        private static BigInteger shift(BigInteger x, int count)
        {
            if (x.words == null)
            {
                if (count <= 0)
                    return valueOf(count > -32 ? x.ival >> (-count) : x.ival < 0 ? -1 : 0);
                if (count < 32)
                    return valueOf((long)x.ival << count);
            }
            if (count == 0)
                return x;
            BigInteger result = new BigInteger(0);
            result.setShift(x, count);
            return result.canonicalize();
        }

        public BigInteger shiftLeft(int n)
        {
            return shift(this, n);
        }

        public BigInteger shiftRight(int n)
        {
            return shift(this, -n);
        }
        public int signum()
        {
            int top = words == null ? ival : words[ival - 1];
            if (top == 0 && words == null)
                return 0;
            return top < 0 ? -1 : 1;
        }

        #region IComparable<T> Members
        private static int compareTo(BigInteger x, BigInteger y)
        {
            if (x.words == null && y.words == null)
                return x.ival < y.ival ? -1 : x.ival > y.ival ? 1 : 0;
            bool x_negative = x.isNegative();
            bool y_negative = y.isNegative();
            if (x_negative != y_negative)
                return x_negative ? -1 : 1;
            int x_len = x.words == null ? 1 : x.ival;
            int y_len = y.words == null ? 1 : y.ival;
            if (x_len != y_len)
                return (x_len > y_len) != x_negative ? 1 : -1;
            return MPN.cmp(x.words, y.words, x_len);
        }
        public int CompareTo(Object obj)
        {
            if (obj is BigInteger)
                return compareTo(this, (BigInteger)obj);
            throw new Exception();
        }

        #endregion

        public BigInteger[] divideAndRemainder(BigInteger val)
        {
            if (val.isZero())
                throw new ArithmeticException("divisor is zero");

            BigInteger[] result = new BigInteger[2];
            result[0] = new BigInteger();
            result[1] = new BigInteger();
            divide(this, val, result[0], result[1], TRUNCATE);
            result[0].canonicalize();
            result[1].canonicalize();
            return result;
        }
    }// end for class
}
